\begin{abstract}
We study how to spread $k$ tokens of information to every node on an
$n$-node dynamic network, the edges of which are changing at each
round. This basic {\em gossip problem}\/ can be completed in $O(n +
k)$ rounds in any static network, and determining its complexity in
dynamic networks is central to understanding the algorithmic limits
and capabilities of various dynamic network models.  Our focus is on
token-forwarding algorithms, which do not manipulate tokens in any way
other than storing and forwarding them.

We first consider the {\em adaptive} adversarial model where in each
round, each node first chooses a token to broadcast to all its
neighbors (without knowing who they are), and then an online adversary
chooses an arbitrary connected communication network for that round
with the knowledge of the tokens chosen by each node. We show that
$\Omega(n + nk/\log n)$ rounds are needed for any randomized
(centralized or distributed) token-forwarding algorithm, thus
resolving an open problem raised in~\cite{kuhn+lo:dynamic}. The bound
applies to a wide class of initial token distributions, including {\em
  well-mixed}\/ ones in which each node has each token independently
with a constant probability.

Our result for the adaptive adversarial model motivates us to study the
{\em oblivious} adversarial model where in each round, the adversary is
required to lay down the network first, and each node then chooses a
possibly distinct token to send to each of its neighbors. We propose a
simple randomized distributed algorithm where in each round, along
every edge $(u,v)$, a token selected uniformly at random from the
symmetric difference of the sets of tokens held by node $u$ and node
$v$ is exchanged. We prove that starting from any well-mixed
distribution of tokens, this algorithm solves the gossip problem in
$O((n+k)\log n)$ rounds with high probability. We then show how the
above uniform selection problem can be solved with $O(\log^{1.5} n)$
bits of communication, making the overall algorithm
communication-efficient.

We next present a centralized algorithm that solves the gossip problem
for every initial distribution in $O((n + k)\log^2 n)$ rounds against
an offline adversary that fixes the communication networks for each
round in advance. Finally, we present an $O(n \min\{k, \sqrt{k \log
  n}\})$-round centralized algorithm against an offline adversary
where each node can only broadcast a single token to all of its
neighbors in each round.
\end{abstract}

\junk{
We next present two fast algorithms that can solve the gossip problem
in $O((n + k)\log^2 n)$ rounds with high probability, which is within
a polylogarithmic factor of the best possible time. Our first
algorithm is a {\em distributed randomized}\/ algorithm that works for
any well-mixed distribution under an oblivious adversary.  A key
ingredient of this algorithm is an $O(\log n)$-bit protocol for
sampling uniformly at random from the symmetric difference of two sets
stored at two communicating nodes, a result that may be of independent
interest in communication complexity.  Our second algorithm is
centralized and offline, and solves gossip for every starting
distribution in $O((n + k)\log^2 n)$ rounds for any dynamic network.
Both of these upper bounds assume that each node can send a distinct
message to each of its neighbors in each round.  We also present
weaker upper bounds for the model where each node can only broadcast a
single message to all of its neighbors in each round.
}

\junk{ 
We present two polynomial-time centralized token-forwarding algorithms
for $k$-gossip in this offline setting: (1) an $O(\min\{nk, n\sqrt{k
  \log n}\})$ round algorithm, and (2) an $(O(n^\eps), O(\log n))$
bicriteria approximation algorithm, for any $\eps > 0$, which means
that our algorithm completes in $O(n^\eps)$ times the optimal number
of rounds and the number of tokens transmitted on any edge is $O(\log
n)$ in each round.
}
